This invention relates to an information processing method and device, and a program supply medium. Particularly, it relates to an information processing method and device for estimating or measuring a parameter using observation data, and a program supply medium for supplying a processing program based on the estimation or measurement method.
In a system for measuring or estimating a parameter of a target system using observation data as an input, because of uncertainty (noise component) of input data or insufficiency of observation data for the parameter to be estimated, the value of the parameter to be estimated is often inappropriate with respect to the actual parameter.
In order to solve this problem, the Kalman filter or a filter for recursive estimation derived therefrom is used, which is described in R. E. Kalman, xe2x80x9cA New Approach to Linear Filtering and Prediction Problemsxe2x80x9d, Trans. ASME-J. Basic Eng., pp.35-45, March 1960.
As the filter for recursive estimation, the Kalman filter is frequently used for a linear system. For an application with a nonlinear system, the extension of the Kalman filter or EKF is the best known filter. This extension of Kahnan filter (EKF) is described in A. Gelb, xe2x80x9cApplied Optical Estimationxe2x80x9d, The Analytic Science Corp., 1974. Also, there are employed the unscented filter, described in S. J. Julier, et al., xe2x80x9cA New Extension of the Kalman Filter to Nonlinear Systemsxe2x80x9d, Proc. Of AeroSense: The 11th International Symposium on Aerospace/Defense Sensing, Simulation and Controlxe2x80x9d, and the pseudo Kalman filter, described in T. Vileville and P. Sanders, xe2x80x9cUsing Pseudo Kalman Filters in the Presence of Constraints, Application to Sensing Behavioursxe2x80x9d, Technical Report 1669, INRIA-Sophia, Valbonne, France, 1992.
While the recursive estimation filter such as the Kalman filter is adapted for estimating the current state variable (parameter) using the current observation value, there is also known a smoother for estimating the past state variable using the current observation value. Hereinafter, the recursive estimation filter such as the Kalman filter will be first described and then the smoother will be described.
The Kalman filter has an efficient minimum square method mounted thereon and is capable of estimating the past, current and future states. It is also capable of estimating a state variable which lacks information and is capable of updating not only the state variable to be estimated but also the error covariance value representing the accuracy of estimation. Therefore, it is known as a robust estimation method.
The Kalman filter is one of the recursive estimation filters. The recursive estimation filter constantly updates the estimation value using only the latest data from continuously inputted observation values. FIG. 1 shows the schematic structure of the recursive estimation filter. This recursive estimation filter includes a prediction section 131 for predicting a motion and an update section 132 for updating predicted data, and carries out estimation by alternately repeating prediction at the prediction section 131 and update at the update section 132.
FIG. 2 is a block diagram showing the schematic structure of a Kalman filter 120 as one recursive estimation filter. First, a set of state variables to be estimated is described as a state vector x. If there are n units of state variables, the state vector x is the n-th order vector. The state vector x of the k-th cycle (one cycle corresponds to the observation cycle) is described as the state vector Xk. The predication process for predicting the next state is expressed by the following equation (1). In the following equation, the vector is described with bold characters. The linear time differentiation of the vector is described with a dot (.) attached to its upper part, and the quadratic time differentiation is described with two dots (..) attached to its upper part.
Xk+1=Akxk+Wkxe2x80x83xe2x80x83(1)
In this case, the matrix Ak is a state transition matrix of the k-th cycle, which is an nxc3x97n matrix. wk represents the prediction process noise generated in the prediction process and is assumed to be the normally distributed Gaussian noise.
The observation process is expressed by the following equation (2).
yk=Hkxk+vkxe2x80x83xe2x80x83(2)
The covariance matrices of the process noise generated in the processes of the equations (1) and (2) are described as Qk and Pk, respectively.
In the equation (2), yk represents the observation vector, which represents the vector of a set of observation values of the k-th cycle, and Hk represents the observation matrix of the k-th cycle. The observation vector yk need not be of the same order as the state vector. If it is assumed that the observation vector yk is of the m-th order, the observation matrix Hk is an mxc3x97n matrix. vk represents the observation noise generated in the observation process, which is assumed to be the Gaussian noise.
The Kalnan filter 120 repeats prediction and update so as to carry out estimation. In this case, the state vector estimated before update is described by the following formula (3) and the estimated state vector after update is described by the following formula (4).
{circumflex over (x)}xe2x88x92kxe2x80x83xe2x80x83(3)
{circumflex over (x)}kxe2x80x83xe2x80x83(4)
The hat mark ({circumflex over ( )}) attached to the upper part in the formulas (3) and (4) indicates that it is an estimation value. In the following text, however, description of xxe2x88x92k({circumflex over ( )}) and xk({circumflex over ( )}) is used.
The above-described Pk is assumed to represent the estimated error covariance after update. The estimated error covariance before update is described by the following formula (5).
Pxe2x88x92kxe2x80x83xe2x80x83(5)
On the foregoing assumption, the processing at the prediction section 131 will be described. As shown in FIG. 2, in the processing e1 at the prediction section 131, the following prediction of the state is carried out on the basis of the equation (6).
{circumflex over (x)}xe2x88x92k=Akxe2x88x921{circumflex over (x)}kxe2x88x921xe2x80x83xe2x80x83(6)
In the processing e2 at the prediction section 131, the following estimated error covariance Pxe2x88x92k is carried out on the basis of the equation (7).
Pxe2x88x92k=Akxe2x88x921Pkxe2x88x921Akxe2x88x921T+Qkxe2x88x921xe2x80x83xe2x80x83(7)
In this equation, Akxe2x88x921T represents the transported matrix of the state transition matrix Akxe2x88x921.
Next, the processing at the update section 132 will be described. In the processing c1 at the update section 132, the Kalman gain Kk is calculated on the basis of the following equation (8).
Kk=Pxe2x88x92kHkT(HkPxe2x88x92kHkT+Rk)xe2x88x921xe2x80x83xe2x80x83(8)
In this equation, HkT represents the transported matrix of the observation matrix Hk and ( )xe2x88x921 represents the inverse matrix of the matrix within ( ).
In the processing c2 at the update section 132, estimation of the state variable is updated on the basis of the following equation (9) using the observation value inputted to the update section 132.
{circumflex over (x)}={circumflex over (x)}xe2x88x92k+Kk(ykxe2x88x92Hk{circumflex over (x)}xe2x88x92k)xe2x80x83xe2x80x83(9)
In the processing c3 at the update section 132, the estimated error covariance Pk is updated on the basis of the following equation (10).
Pk=(Ixe2x88x92KkHk)Pxe2x88x92kxe2x80x83xe2x80x83(10)
In this equation, I represents the unit matrix of the nxc3x97n dimension.
With the Kalman filter 120 as described above, it is assumed that both the prediction process and the observation process are linear. Actually, however, these processes are often nonlinear. In order to cope with this, a derived filter such as the above-described EKF (extension of the Kalman filter) is proposed. The most frequently used EKF will now be described.
In the EKF, the prediction process is expressed by the following equation (11) (corresponding to the formula (1) of the Kalman filter 120), and the observation process is expressed by the following equation (12) (corresponding to the equation of the Kalman filter 120).
xk+1=f(xk)+wkxe2x80x83xe2x80x83(11)
yk=h(xk)+vkxe2x80x83xe2x80x83(12)
In this case, f represents the nonlinear state transition matrix and h represents the nonlinear observation matrix.
With respect to the actual estimation framnework in the EKF, the processing corresponding to the processing e1 of the Kalman filter 120 (FIG. 2) is expressed by the following equation (13).
xe2x80x83{circumflex over (x)}xe2x88x92k=f({circumflex over (x)}kxe2x88x921)xe2x80x83xe2x80x83(13)
The processing corresponding the processing e2 of the Kalman filter 120 (FIG. 2) is expressed by the following equation (14).
{circumflex over (x)}k={circumflex over (x)}xe2x88x92k+Kk(ykxe2x88x92h({circumflex over (x)}xe2x88x92k))xe2x80x83xe2x80x83(14)
The state transition matrix Ak is expressed by the following equation (15) and the observation matrix Hk is expressed by the following equation (16).                               Ak                      (                          i              ,              j                        )                          =                              ∂                                          f                                  (                  i                  )                                            ⁡                              (                                                      x                    ^                                    k                                )                                                          ∂                          x                              k                ⁡                                  (                  j                  )                                                                                        (        15        )                                          H                      k            ⁡                          (                              i                ,                j                            )                                      =                              ∂                                          h                                  (                  i                  )                                            ⁡                              (                                                      x                    ^                                    k                                )                                                          ∂                          x                              k                ⁡                                  (                  j                  )                                                                                        (        16        )            
In this case, Ak(i,j) represents the matrix elements of the i-th row and the j-th column of the state transition matrix Ak, and is calculated by partially differentiating the i-component of the function f with the j-component of the state variable xk. Hk(i,j) represents the matrix elements of the i-th row and the j-th colm-n of the observation matrix Hk, and is calculated by partially differentiating the i-component of the function h with the j-component of the state variable xk. Except for these features, the EKF is similar to the Kalman filter 120.
In filtering by the Kalman filter or the like as described above, the current state variable (parameter) is estimated by using the current observation value, but the estimation value might be affected by a sudden large noise. On the other hand, in smoothing, the past state variable (parameter) is estimated by using the current observation value. The Kalman smoother utilizing the technique of the Kalman filter is technically established already. The smoother is described in: Toru Katayama, xe2x80x9cApplied Kalman Filterxe2x80x9d, Asakura Shoten; Gelb ed., xe2x80x9cApplied Optimal Estimationxe2x80x9d, MIT Press; and R. G. Brown and P. Y. Hwang, xe2x80x9cIntroduction to Random Signals and Applied Kalman Filteringxe2x80x9d, John Wiley and Sons, Inc.
Using the smoother, robustness against any sudden change of the observation value is realized. In the case where the observation data is degenerated, the accuracy is often improved by smoothing even though estimation by filtering is difficult.
As such smoother, there are three types, that is, a fixed-point smoother, a fixed-interval smoother and a fixed-lag smoother which are suitable for different applications in accordance with their respective characteristics. The fixed-point smoother is suitable for estimation of an initial value, and the fixed-interval smoother is suitable for batch processing after gathering of a set of time series data. The fixed-lag smoother is characterized in that the parameter is estimated constantly with a lag of a predetermined period (time period L) with respect to the observation data. That is, it is a smoother for estimating the state variable of the time period txe2x88x92L by using the observation data obtained during the time period t. By using this, substantially real-tune processing can be carried out in a system which allows a predetermined delay. For example, in the case where processing is carried out by the fixed-lag smoother using observation data obtained from an NTSC image, if there is a lag L=10 frames, a delay of {fraction (1/30)}xc3x9710=⅓ seconds or more is simply generated. In a system which allows this delay, the smoother for improving the estimation accuracy is useful.
However, in the above-described conventional technique, when a boundary condition is added to the parameter as the estimation target, it is impossible or very difficult to take that condition into consideration with the Kalman filter.
Specifically, with the conventional recursive estimation filter such as the Kalman filter or the Kalnan smoother having the Kalnan filter operating inside thereof, only the optimal estimation value in a state space having no constraint can be found. With the pseudo Kalman filter described in T. Vileville and P. Sanders, xe2x80x9cUsing Pseudo Kalman Filters in the Presence of Constraints, Application to Sensing Behavioursxe2x80x9d, Technical Report 1669, INRIA-Sophia, Valbonne, France, 1992, optimal estimation under a constraint expressed by an equation, but a constraint expressed by an inequality and a boundary condition cannot be handled. Strictly, on the assumption that the resolution is known to be necessarily present on the boundary in an inequality or under a boundary condition, the pseudo Kabnan filter can handle the constraint expressed by the inequality and the boundary condition. However, such assumption is not necessarily secured for all problems.
Therefore, even when the state variable has a boundary condition, it is not guaranteed at all that the estimation value from the conventional recursive filter falls within the condition or that the resultant estimation value is the optimum value. The Kalman smoother cannot handle a boundary condition since it basically causes the Kalman filter to operate inside thereof.
A specific example in which a constraint is necessary will now be described with reference to FIG. 3. In FIG. 3, it is assumed that an arm 42 of a target or an object (person) 41 is observed from a direction p (direction from the right lateral side of the object 41) and from a direction i perpendicular to the direction p. The arm 42 in FIG. 3 includes a wrist joint 42a, an elbow joint 42b and a shoulder joint 42c. FIGS. 4A and 4B show a continuous change from an image i1 to an image i2 in the case where the arm 42 of the object 41 in FIG. 3 is observed from the direction i. An image p1 of FIG. 5A and an image p2-a of FIG. 5B show the images of the arm 42 of the object 41 in the case where it is picked up from the direction p when the image i1 of FIG. 4A and the image i2 of FIG. 4B are observed. In the case where the data of the image p1 of FIG. 5A is correctly estimated with respect to the data of the image i1 of FIG. 4A and where the image p2-a of FIG. 5B corresponds to the actual posture with respect to the data of the image i2 of, the actual posture might be erroneously estimated as an image p2-b of FIG. 5C if the prediction process is not appropriate.
Thus, the estimation system might return the image p2-b as the estimation value. This is because two-dimensional information lacks information of depth. However, since it is known that the elbow cannot be bent in the reverse direction, the solution that the image p2-a corresponds to the actual posture can be obtained on the basis of that knowledge. The conventional recursive filter cannot return the optimum value under such boundary condition, and the smoother using such recursive filter cannot carry out optimal estimation, either.
It is also conceivable to apply the smoother for multi-joint motion estimation. However, it is necessary to consider what parameter should be the estimation target for prediction of a precise motion.
In view of the foregoing status of the art, it is an object of the present invention to provide an information processing method and device and a program supply medium which enable effective processing even in the case where an estimation target parameter has a boundary condition with respect to a recursive estimation filter for predicting a state variable (parameter) such as motion information of an object.
It is another object of the present invention to provide an information processing method and device and a program supply medium which enable effective processing even in the case where an estimation target parameter has a boundary condition with respect to a recursive smoother for estimating the past state variable (parameter) from the current observation value and which enable more precise parameter estimation in application to multi-joint motion estimation or the like.
In an information processing method and device according to the present invention, when estimating a state variable of a target on the basis of a previously estimated state variable and an observation value, a prediction value of a next state variable is found on the basis of the previously estimated state variable, and the state variable is updated on the basis of the found prediction value and the observation value so as to obtain an update value and output the update value as an estimation value. As the update value, depending on the case, an update value is used which minimizes the Mahalanobis distance from the prediction value in the state space and the square sum or the absolute value sum of the Mahalanobis distance from the observation value in the observation space under a boundary condition.
In this case, the update value of the state variable is found on the basis of the prediction value and the observation value, and it is checked whether the resultant update value meets the boundary condition or not. When the update value does not meet the boundary condition, a new update value is found which minimizes the Mahalanobis distance from the prediction value in the state space and the square sum or the absolute value sum of the Mahalanobis distance from the observation value in the observation space under the boundary condition. A minimum square method is applied to the case where the estimation target parameter (state variable) has a boundary condition. To find an update value under the restraining condition, quadratic programming or nonlinear programming is used.
Thus, the state variable of motion information or torque of a multi-joint object can be estimated under the restraining condition such as a boundary condition.
Also, in an information processing method and device according to the present invention, when estimating a state variable at a predetermined position on the time base with respect to a target on the basis of a previously estimated state variable and an observation value, filtering processing is sequentially repeated L times, including processing for finding a prediction value of the state variable at that time point on the basis of an update value of a state variable immediately before and for finding an update value which minimizes the Mahalanobis distance from the prediction value in the state space and the square sum or the absolute value sum of the Mahalanobis distance from the observation value in the observation space under a boundary condition. The state variable at the predetermined position on the time base is estimated on the basis of the value obtained in the filtering processing of each time.
The filtering processing is sequentially carried out over a predetermined range from the predetermined position on the time base to the future.
As the filtering processing, the prediction value of the state variable at that time point is found on the basis of the update value of the state variable immediately before, and the update value of the state variable is found on the basis of the resultant prediction value and the observation value at that time point. Whether the update value meets the boundary condition or not is checked. When the update value does not meet the boundary condition, a new update value is found which minimizes the Mahalanobis distance from the prediction value in the state space and the square sum or the absolute value sum of the Mahalanobis distance from the observation value in the observation space under the boundary condition.
In an information processing method and device according to the present invention, when estimating a state variable at a predetermined position on the time base with respect to a target on the basis of an estimation value of a previously estimates state variable and an observation value, filtering processing is sequentially repeated L times, including processing for finding a prediction value of motion information and a prediction value of torque of the target at that time point on the basis of an update value of motion information and an update value of torque of the target immediately before and for finding the update value of motion information and the update value of torque at that time point on the basis of the resultant prediction values, the observation value of motion information of the target and the observation value of torque. The state variable at the predetermined position on the time base is estimated on the basis of the value obtained in the filtering processing of each time.
With the information processing method and device according to the present invention, when estimating a state variable of a target on the basis of a previously estimated state variable and an observation value, a prediction value of a next state variable is found on the basis of the previously estimated state variable, and the state variable is updated on the basis of the found prediction value and the observation value so as to obtain an update value and output the update value as an estimation value. As the update value, depending on the case, an update value is used which minimizes the Mahalanobis distance from the prediction value in the state space and the square sum or the absolute value sum of the Mahalanobis distance from the observation value in the observation space under a boundary condition. Thus, optimal estimation of the state variable can be carried out under the boundary condition.
Also, the first update value of the state variable is found on the basis of the prediction value and the observation value, and it is checked whether the resultant update value meets the boundary condition or not. When the update value does not meet the boundary condition, a new update value is found which minimizes the Mahalanobis distance from the prediction value in the state space and the square sum or the absolute value sum of the Mahalanobis distance from the observation value in the observation space under the boundary condition. Therefore, as the first update value is outputted as the estimation value in the case where the boundary condition is met, computation requiring large burden for finding the new estimation value is not necessary and the overall burden of the computational processing is reduced.
Moreover, with information processing method and device according to the present invention, when estimating a state variable at a predetermined position on the time base with respect to a target on the basis of a previously estimated state variable and an observation value, filtering processing is sequentially repeated L times, including processing for finding a prediction value of the state variable at that time point on the basis of an update value of a state variable immediately before and for finding an update value which minimizes the Mahalanobis distance from the prediction value in the state space and the square sum or the absolute value sum of the Mahalanobis distance from the observation value in the observation space under a boundary condition. The state variable at the predetermined position on the time base is estimated on the basis of the value obtained in the filtering processing of each time. Thus, optimal estimation of the state variable can be carried out under the boundary condition. Also, optimal estimation of the state variable (parameter) can be carried out with respect to an abrupt motion or a motion accompanying a sudden large noise.
In the filtering processing, the first update value of the state variable is found on the basis of the resultant prediction value and the observation value, and whether the update value meets the boundary condition or not is checked. When the update value does not meet the boundary condition, a new update value is found which minimizes the Mahalanobis distance from the prediction value in the state space and the square sum or the absolute value sum of the Mahalanobis distance from the observation value in the observation space under the boundary condition. Therefore, as the first update value is outputted as the estimation value in the case where the boundary condition is met, computation requiring large burden for finding the new estimation value is not necessary and the overall burden of the computational processing is reduced.
Also, with the information processing method and device according to the present invention, when estimating a state variable at a predetermined position on the time base with respect to a target on the basis of an estimation value of a previously estimates state variable and an observation value, filtering processing is sequentially repeated L times, including processing for finding a prediction value of motion information and a prediction value of torque of the target at that time point on the basis of an update value of motion information and an update value of torque of the target immediately before and for finding -the update value of motion information and the update value of torque at that time point on the basis of the resultant prediction values, the observation value of motion information of the target and the observation value of torque. The state variable at the predetermined position on the time base is estimated on the basis of the value obtained in the filtering processing of each time. Thus, more precise prediction of a motion is made possible. Specifically, since the prediction model more resembles the actual model, robust estimation can be carried out even in the case where there is a large change in the data parameter (state variable) of the sampled continuous data. For the same reason, the accuracy of estimation can be unproved.
Moreover, since estimation of the state variable is carried out by using motion information and torque information for the state variable, the motion information and torque information of a multi-joint object can be properly estimated under the boundary condition. The accuracy of estimation in the direction of depth can be improved, which was conventionally difficult in the motion estimation from a single-view image. It can be applied for the single-camera construction of an optical motion capture system (motion measurement system), which currently requires a plurality of cameras. Thus, the complicated operation such as calibration is not necessary. Also, three-dimensional motions of persons and animals can be reproduced from archives such as the past movie films and video pictures.
These effects can be obtained not only in the case where a single-view image sequence is used as an input but also in the case where images from a plurality of cameras or inputs from other sensors such as an angular speedometer and an angular accelerometer are used.